package org.example;
/**
 *
 * 时间复杂度:O(N^2)
 *     最坏情况下：逆序5，4，3，2，1
 *     最好情况下：本身就是有序的1，2，3，4，5   O(n)
 *     如果数据越有序，直接插入排序越快
 * 空间复杂度:O(1)
 * 稳定性:稳定
 * 本身如果是一个稳定的排序，那么可以实现为不稳定的
 * 但是如果一个排序本身不稳定，不能实现为一个稳定的排序
 */
public class Sort {
    public  static  void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= 0 ; j--) {
                if(array[j]>tmp){
                    array[j+1] = array[j];
                }
                else {
                    array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }


    /**
     * 希尔排序
     * 这种排序是直接插入排序的优化
     *
     *稳定性：不稳定
     * 时间复杂度：不好算
     * 空间复杂度：O(1)
     * @param array
     */
    public static  void shellSort(int[] array){
        int gap = array.length;
        while(gap>1){
            gap/=2;
            shell(array,gap);
        }

    }
    private static void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i-gap;
            for (; j >= 0 ; j-=gap) {
                if(array[j]>tmp){
                    array[j+gap] = array[j];
                }
                else {
                    array[j+gap] = tmp;
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }



}


